//defining the class tree, Node, modules Node and End

abstract class Tree[+T]

//Prefixing a formal type parameter with a + indicates that subtyping is covariant
//(flexible) in that parameter, i.e., any subtype can also be used.

case class Node[+T](value: T, left: Tree[T], right: Tree[T]) extends Tree[T] {
  override def toString = "->(" + value.toString + " " + left.toString + " " + right.toString + ")"
}

case object End extends Tree[Nothing] {
  override def toString = "."
}

object Node  {
  //def Node[T](value: T): Node[T] = Node(value, End, End)
}

//This code creates the required tree.

//using the above snippet, we would create balanced binary tree,given number of nodes and a value to fill in all the nodes. 

object Tree {
  def Balanced[T](nodes: Int, value: T): List[Tree[T]] =  {
    if(nodes < 1)
      List(End)
    else if(nodes % 2 == 1)
    {
      val part = Balanced(nodes / 2, value)
      part.flatMap(l => part.map(r => Node(value, l, r)))
    }
//The flatMap operator is similar to map, but it takes a function returning a list
//of elements as its right operand. It applies the function to each list element
//and returns the concatenation of all function results.

    else  //even number of nodes
    {
      val smallpart = Balanced((nodes - 1) / 2, value)
      val bigpart = Balanced((nodes - 1) / 2 + 1, value)
      smallpart.flatMap(l => bigpart.flatMap(g => List(Node(value, l, g), Node(value, g, l))))
    }
  }
}